/**
 * 堆结构，默认是大顶堆
 * 如果需要小顶堆，实现 comparator 方法时，若 e1 > e2 返回-1, e1 < e2 返回1
*/
#include <stdlib.h>

#ifndef HEAP
#define HEAP

#ifndef HeapElementType
#define HeapElementType int
#endif

// 为能直接把其他的数组直接调整为堆，这里不使用[0]存放哨兵的方法，从[0]开始存储元素
typedef struct Heap Heap;
struct Heap {
    HeapElementType* data; // 存储元素的数组
    int size; // 元素个数
    int capacity; // 最大容量
    // 堆元素比较器
    int (*comparator)(HeapElementType e1, HeapElementType e2);
};

// 从 startIdx 开始的位置向下调整，让数组变为堆
void percDown(Heap* h, int startIdx) {
    int parent, child;
    // 取出 startIdx 处存放的值
    HeapElementType temp = h->data[startIdx];
    // 向下（左右儿子）找可以正确存放 temp 的合适位置
    for (parent = startIdx; parent*2+1 < h->size; parent = child /* 顺着调整过的儿子节点继续向下 */) {
        child = parent*2+1;
        if ((child != h->size - 1) && h->comparator(h->data[child], h->data[child+1]) < 0) {
            // 有右儿子，且右儿子比较大
            child++; // 指向右儿子
        }
        if (h->comparator(temp, h->data[child]) >= 0) {
            // temp 比它的左右儿子都大，即找到了合适位置，不用再往下找了
            break;
        }
        // 把更大的子节点复制到父节点位置，即把大的数往上调
        h->data[parent] = h->data[child];
    }
    h->data[parent] = temp;
}

Heap* createHeap(int capacity, int (*comparator)(HeapElementType e1, HeapElementType e2)) {
    Heap* h = calloc(1, sizeof(Heap));
    h->data = calloc(capacity, sizeof(HeapElementType));
    h->size = 0;
    h->capacity = capacity;
    h->comparator = comparator;
    return h;
}

// 从已知数组中创建堆，创建堆时把数组 data 调整为堆
Heap* createHeapFromData(HeapElementType* data, int size, int capacity, int (*comparator)(HeapElementType e1, HeapElementType e2)) {
    Heap* h = calloc(1, sizeof(Heap));
    h->data = data;
    h->size = size;
    h->capacity = capacity;
    h->comparator = comparator;
    // 从最后一棵子树的位置开始到根节点0，向下调整堆。
    // 默认所有叶子节点都已经是堆
    for (int sidx=(size-1)/2; sidx >= 0; sidx--) {
        percDown(h, sidx);
    }
    return h;
}

void freeHeap(Heap* h) {
    free(h->data);
    free(h);
}

int isFullHeap(Heap* h) {
    return h->size+1 > h->capacity;
}

int isEmptyHeap(Heap* h) {
    return h->size < 1;
}

void insertHeap(Heap* h, HeapElementType item) {
    if (isFullHeap(h)) {
        printf("Heap Full");
        return;
    }
    int i = h->size++;
    // 调整:比较item，与item的父节点（父节点下标=(i-1)/2），若大于父节点，把父节点往下移动
    for (; i > 0 && h->comparator(item, h->data[(i-1)/2]) > 0; i=(i-1)/2) {
        h->data[i] = h->data[(i-1)/2];
    }
    h->data[i] = item;
}

HeapElementType deleteHeap(Heap *h) {
    if (isEmptyHeap(h)) {
        printf("Heap Empty\n");
        HeapElementType error;
        return error;
    }
    // 取出最大的节点
    HeapElementType maxItem = h->data[0];
    // 先把最后一个节点放入第0个节点位置
    h->data[0] = h->data[--h->size];
    // 因为动了第0个位置，从0开始向下调整堆
    percDown(h, 0);
    return maxItem;
}

// HeapElementType deleteHeap(Heap *h) {
//     if (isEmptyHeap(h)) {
//         printf("Heap Empty\n");
//         HeapElementType error;
//         return error;
//     }
//     // 取出最大的节点
//     HeapElementType maxItem = h->data[1];
//     // 先把最后一个节点放入第一个节点位置
//     HeapElementType temp = h->data[h->size--];
//     // 再调整堆
//     int parent, child;
//     // 为temp找一个位置
//     // parent*2 < h->size 判断是否有左儿子
//     for (parent = 1; parent*2 <= h->size; parent = child) {
//         child = parent * 2;
//         if ( (child != h->size) && h->comparator(h->data[child], h->data[child+1]) < 0) {
//             // child != h->size 是否有右儿子
//             // 找到左右节点中更大的节点
//             child++;
//         }
//         // 根已经大于等于孩子节点，结束循环
//         if (h->comparator(temp, h->data[child]) >= 0) {
//             break;
//         }
//         // 把更大的子节点复制到父节点位置
//         h->data[parent] = h->data[child];
//     }
//     h->data[parent] = temp;
//     return maxItem;
// }

#endif
